package com.future;

import com.future.util.TreeNode;

/**
 * Description: 1373. 二叉搜索子树的最大键值和
 * img/Solution_1373.png
 *
 * @author weiruibai.vendor
 * Date: 2023/1/4 10:07
 */
public class Solution_1373 {

    private static Solution_1373 instance = new Solution_1373();

    public static void main(String[] args) {
        /**
         * 输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
         * 输出：20
         * 解释：键值为 3 的子树是和最大的二叉搜索树。
         */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);

        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(5);

        root.right.right.left = new TreeNode(4);
        root.right.right.right = new TreeNode(6);

        /**
         * [4,3,null,1,2]
         */
        root = new TreeNode(4);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(2);
        //System.out.println(instance.maxSumBST(root));
        /**
         * [5,4,8,3,null,6,3]
         */

        /**
         * [4,8,null,6,1,9,null,-5,4,null,null,null,-3,null,10]
         * 14
         */
        root = new TreeNode(4);
        root.left = new TreeNode(8);
        root.left.left = new TreeNode(6);
        root.left.left.left = new TreeNode(9);

        root.left.right = new TreeNode(1);
        root.left.right.left = new TreeNode(-5);
        root.left.right.left.right = new TreeNode(-3);
        root.left.right.right = new TreeNode(4);
        root.left.right.right.right = new TreeNode(10);
        if (instance.maxSumBST(root) != 14) {
            throw new RuntimeException("error");
        }
        /**
         * [9,2,3,null,2,null,null,3,null,-5,4,null,1,null,10]
         * 14
         */
        /**
         * [1,null,10,-5,20]
         * 25
         */
        root = new TreeNode(1);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(-5);
        root.right.right = new TreeNode(20);
        if (instance.maxSumBST(root) != 25) {
            throw new RuntimeException("error");
        }
        /**
         * [9,2,3,null,2,null,null,3,null,-5,4,null,1,null,10]
         * 14
         */
        root = new TreeNode(9);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(3);
        root.left.right.left.left = new TreeNode(-5);
        root.left.right.left.left.right = new TreeNode(1);
        root.left.right.left.right = new TreeNode(4);
        root.left.right.left.right.right = new TreeNode(10);

        root.right = new TreeNode(3);
        root.right.right = new TreeNode(10);
        if (instance.maxSumBST(root) != 14) {
            throw new RuntimeException("error");
        }
    }

    /**
     * 找和最大的搜索二叉树！！！并不是找节点最多的搜索二叉树！！
     *
     * @param root
     * @return
     */
    public int maxSumBST(TreeNode root) {
        int sum = calcMaxValue(root).maxSearchSum;
        return Math.max(sum, 0);
    }

    private Msg calcMaxValue(TreeNode root) {
        if (root == null) {
            return new Msg(true, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        if (root.left == null && root.right == null) {
            return new Msg(true, root.val, root.val, root.val, root.val);
        }
        Msg leftMsg = calcMaxValue(root.left);
        Msg rightMsg = calcMaxValue(root.right);
        int sum; // 计算当前节点以及子节点的所有节点值之和
        int maxSearchSum ;
        Integer maxValue;
        Integer minValue;
        boolean isBST;
        /**
         * 不仅仅要比较当前左右子树的满足搜索二叉树
         * 而且要保证左子树的最大值要小于当前节点值
         * 右子树的最小值要大于当前节点值
         */
        if (leftMsg.searchBinaryTree && rightMsg.searchBinaryTree) {
            if (null != root.left && null != root.right
                    && (root.val > root.left.val && root.val < root.right.val)
                    && (root.val > leftMsg.max && root.val < rightMsg.min)) {
                /**
                 * 左右子树非空且符合搜索二叉树
                 */
                isBST = true;
                maxValue = Math.max(leftMsg.max, rightMsg.max);
                minValue = Math.min(leftMsg.min, rightMsg.min);
                sum = root.val + leftMsg.sum + rightMsg.sum;
                /**
                 * 当取当前节点root时，需要计算的是左子树和右子树的所有节点和！！并不是maxSearchSum
                 */
                int max1 = leftMsg.sum + root.val + rightMsg.sum;
                /**
                 * 当不取当前节点root时，就看左右子树哪个大
                 * 综合以上，哪个大取哪个
                 *
                 * 一下情况以此类推
                 */
                maxSearchSum = Math.max(max1, Math.max(leftMsg.maxSearchSum, rightMsg.maxSearchSum));
            } else if (null == root.right
                    && null != root.left && root.left.val < root.val
                    && (root.val > leftMsg.max && root.val < rightMsg.min)) {
                /**
                 * 右子树为空且符合搜索二叉树
                 */
                isBST = true;
                maxValue = root.val;
                minValue = leftMsg.min;
                sum = root.val + leftMsg.sum;
                maxSearchSum = Math.max(root.val + leftMsg.sum, leftMsg.maxSearchSum);
            } else if (null == root.left
                    && null != root.right && root.right.val > root.val
                    && (root.val > leftMsg.max && root.val < rightMsg.min)) {
                /**
                 * 左子树为空且符合搜索二叉树
                 */
                isBST = true;
                maxValue = rightMsg.max;
                minValue = root.val;

                sum = root.val + rightMsg.sum;
                maxSearchSum = Math.max(root.val + rightMsg.sum, rightMsg.maxSearchSum);
            } else if (null == root.left && null == root.right
                    && (root.val > leftMsg.max && root.val < rightMsg.min)) {
                /**
                 * 左右子树都为空
                 */
                isBST = true;
                maxValue = root.val;
                minValue = root.val;
                sum = root.val;
                maxSearchSum = root.val;
            } else {
                /**
                 * 不符合搜索二叉树
                 */
                isBST = false;
                maxValue = null;
                minValue = null;
                maxSearchSum = Math.max(leftMsg.maxSearchSum, rightMsg.maxSearchSum);
                sum = 0;
            }
        } else {
            isBST = false;
            maxValue = 0;
            minValue = maxSearchSum = Math.max(leftMsg.maxSearchSum, rightMsg.maxSearchSum);
            sum = leftMsg.sum + rightMsg.sum + root.val;
        }
        return new Msg(isBST, maxSearchSum, sum, maxValue, minValue);
    }

    /**
     * 返回树的信息
     * 任意节点的左子树中的键值都 小于 此节点的键值。
     * 任意节点的右子树中的键值都 大于 此节点的键值。
     * 任意节点的左子树和右子树都是二叉搜索树。
     */
    class Msg {
        /**
         * 是否是搜索二叉树
         */
        private boolean searchBinaryTree;

        /**
         * 最终答案
         */
        private Integer maxSearchSum;

        /**
         * 当前节点满足条件时，需要把当前节点以及所有的子节点的值都相加
         * sum--记录当前节点以及所有子树的节点值之和
         */
        private Integer sum;

        /**
         * 不仅仅要比较当前左右子树的满足搜索二叉树
         * 而且要保证左子树的最大值要小于当前节点值
         * 右子树的最小值要大于当前节点值
         */
        private Integer max;// 左右子树最大值
        private Integer min;// 左右子树最小值

        public Msg(boolean searchBinaryTree, Integer maxSearchSum, Integer sum, Integer max, Integer min) {
            this.searchBinaryTree = searchBinaryTree;
            this.maxSearchSum = maxSearchSum;
            this.sum = sum;
            this.max = max;
            this.min = min;
        }

        @Override
        public String toString() {
            return "Msg{" +
                    "isBST=" + searchBinaryTree +
                    ", max=" + max +
                    ", min=" + min +
                    ", maxSearchSum=" + maxSearchSum +
                    ", sum=" + sum +
                    '}';
        }
    }

}

